


/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function(k, nums) {
    this.k = k;
    this.min_heap = new MinHeap();
    for (let num of nums) {
        this.add(num)
    }

};

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function(val) {
    this.min_heap.insert(val);
    // if(this.min_heap.size() > this.k){
    //     this.min_heap.deleteMin();
    // }
    return this.min_heap.peek();
};

class MinHeap {
    constructor() {
        this.data = [];
    }
    compare(a,b){
        return a - b;
    }
    insert(val){
        this.data.push(val);
        this.shiftUp();
    }
    size(){
        return this.data.length;
    }
    deleteMin(){
        if(this.size()){
            let res = this.data[0];
            if(this.size() > 1){
                this.shiftDown();
            }else{
                this.data = [];
            }
            return res;
        }else {
            return null;
        }
    }
    peek(){
        if(this.size()){
            return this.data[0]
        }else {
            return null;
        }
    }
    shiftDown(){
        this.data[0] = this.data[this.size() - 1];
        this.data.pop();
        let min_index = 0;
        let left_index = 2 * min_index + 1;
        let right_index = 2 * min_index + 2;
        let temp = null;
        while (left_index < this.size()){
            if(right_index < this.size()){
                if(this.compare(this.data[left_index],this.data[right_index]) < 0){
                    temp = left_index;
                }else {
                    temp = right_index;
                }
            }else{
                temp = left_index;
            }
            if(this.compare(this.data[min_index],this.data[temp]) > 0){
                this.swap(min_index,temp);
                min_index = temp;
                left_index = 2 * min_index + 1;
                right_index = 2 * min_index + 2;
            }else {
                break;
            }
        }
    }
    shiftUp(){
        let child_index = this.data.length - 1;//>0
        let parent_index = null;//>= 0
        while (child_index > 0){
            parent_index = (child_index -1)/2;
            if(this.compare(this.data[child_index],this.data[parent_index]) < 0){
                this.swap(child_index,parent_index);
                child_index = parent_index;
            }else {
                break;
            }
        }
    }
    swap(i,j){
        [this.data[i],this.data[j]] = [this.data[j],this.data[i]]
    }
}

let  kthLargest = new KthLargest(2, [0]);
console.log(kthLargest)
kthLargest.add(-1)
console.log(kthLargest)
kthLargest.add(1)
console.log(kthLargest)
kthLargest.add(-2)
console.log(kthLargest)
kthLargest.add(-4)
console.log(kthLargest)
// console.log(kthLargest.add(1));
// console.log(kthLargest)
// console.log(kthLargest.add(-2));
// console.log(kthLargest)
// console.log(kthLargest.add(-4));
// console.log(kthLargest)
// console.log(kthLargest.add(3));
// console.log(kthLargest)
// console.log(kthLargest.add(10));
// console.log(kthLargest.add(9));
// console.log(kthLargest.add(4));




/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */


// KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
// kthLargest.add(3);   // return 4
// kthLargest.add(5);   // return 5
// kthLargest.add(10);  // return 5
// kthLargest.add(9);   // return 8
// kthLargest.add(4);   // return 8
